1. Technical Field
The present invention relates in general to an improved data processing system and in particular to an improved method and system for managing data access in a data processing system. Still more particularly the present invention relates to an improved method and system for cache memory congruence class management in data processing system.
2. Description of the Related Art
Modern-state-of-the-art data processing systems often utilize a broad spectrum of memory devices. These memory devices are typically classified according to speed of access and, as those skilled in the art will appreciate, there is generally a relationship between the cost of such devices and the speed at which these devices will access data. For example, semiconductor memory devices exist which may be utilized to rapidly access data stored therein; however, the cost of these devices is typically quite high. In contrast, so-called "Direct Access Storage Devices" (DASD) are capable of storing large amounts of data; however, the access time for retrieving data within such devices is generally quite high when compared to semiconductor memory circuits.
Thus, the design of a modern state-of-the-art data processing system incorporates a continuous compromise between cost and speed in terms of the memory devices utilized. It is quite common for such systems to utilize a broad spectrum of memory devices for specific purposes and in a specific manner in an attempt to create a data processing system having the most efficient combination of cost and speed which is possible.
One method which is often utilized by system designers in an attempt to increase the effective speed at which slower memory devices may be accessed is the utilization of a so-called "cache" memory. A cache memory system is utilized to temporarily store small amounts of data within high speed memory in anticipation of an access request for that data. Such cache memory systems are typically quite small in size when compared with overall system memory; however, by choosing the size of a cache memory system carefully and by efficiently determining what data should be stored within cache memory over eighty percent of all data accesses within a system may result in a cache access, greatly enhancing the efficiency of the processor.
One method by which data within a cache memory system is more rapidly accessed and retrieved is the utilization of an associative storage system. An associative storage system is a system in which storage locations within the system are identified by their contents or by a portion of their contents, rather than by names or positions. Thus, if an attempted access of data includes an identification of the data which is sought, an associative storage system utilized as a cache may result in greater efficiency in retrieving that data. Data is often stored within an associative cache memory system utilizing a so-called "hash" function. A hash function is a function which is utilized to transform a search key into a table address. Ideally, different search keys will map to different addresses; however, many hash functions result in situations in which two or more different keys hash to the same table address. Thus, a hashing search typically includes a "collision-resolution" process which deals with such situations. Hashing functions may be utilized in a data processing system to greatly enhance the efficiency of a processor in retrieving selected data within the data processing system.
One application of an associative cache memory and hash function for controlling access to multiple data addresses occurs in situations in which data within a single real memory address is mapped to multiple different virtual memory addresses. For example, in a multi-tasking system a single location within real memory may map to multiple different addresses within different virtual memory spaces, wherein each virtual memory space is associated with a particular task within the multi-tasking system. In such systems, the-virtual memory and real memory addresses often include multiple portions, such as a segment index, a page index and a byte index. A hash function is then typically applied to a particular portion of the system address, such as the byte index.
This technique results in a great deal of efficiency in situations in which the byte index comprises twelve bits. A twelve bit byte index corresponds to 4,096 (4K) different possible addresses and thus, a cache memory system having 4,096 (4K) columns may be efficiently utilized to store references to different virtual memory addresses. By providing a cache memory containing 4 rows and 4K columns, up to four different virtual memory addresses, each having an identical byte index, may be "hashed" to a single column within the cache memory system. In such a system, the single column is referred to as a "congruence class" in that multiple virtual addresses corresponding to a single real address will all map to a single congruence class within a cache memory, if the cache memory is sized appropriately for the address scheme utilized.
However, more advanced data processing systems, such as the International Business Machines Corporation 3090 and 9000 series processors require the utilization of larger cache memories. In such a situation the cache may comprise 4 rows by 32K columns for example and, as a result, additional bits within the virtual memory address are often utilized to hash to a location within the cache memory. By utilizing n additional bits for the hash function those skilled in the art will appreciate that up to 2" different results may occur from the application of the hash function. Thus, eight different virtual memory addresses, each corresponding to a single real memory address, may hash to eight different congruence classes within a cache memory. In such a situation, an attempted processor access of a particular virtual memory address will result in a substantial delay in view of the fact that many different congruence classes must be examined.
Upon reference to the foregoing those skilled in the art will appreciate that a need exists for a method and system wherein multiple virtual memory addresses, each corresponding to a single real memory address, may be hashed to a single congruence class within an enlarged cache memory system.